package leetcodev1.数组;

public class LeetCode31 {

    //这种题理解不了，背一下..
    public void nextPermutation(int[] nums) {
        int i = nums.length - 2;
        //找到第一个i<i+1的数 保证[i+1,n]是降序
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = nums.length - 1;
            //找到第一个nums[j]>nums[i]
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            swap(nums, i, j);
        }
        //没有符合条件的全部reverse
        //有符合条件的翻转部分
        reverse(nums, i + 1);
    }

    public void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int tmp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = tmp;
    }

    //暴力解 三重循环（数组长度不确定）
    public void nextPermutation1(int[] nums) {
        if (nums == null) {
            return;
        }

        //规则1：找到略大于sum的组合
        //规则2：如果sum最大，则sum最小的组合
        int sum = getVal(nums);

    }

    private int getVal(int[] nums) {
        int n = nums.length - 1, index = 0, ret = 0;
        while (n >= 0) {
            ret += nums[n] * Math.pow(10, index);
            index++;
            n--;
        }
        return ret;
    }

}
